A Newton-MR Algorithm with Complexity Guarantee for Non-Convex Problems

Abstract: Classically, the conjugate gradient (CG) method has been the dominant solver in most inexact Newton-type methods for unconstrained optimization. In this talk, we consider replacing CG with the minimum residual method (MINRES), which is often used for symmetric but possibly indefinite linear systems. We show that MINRES has an inherent ability to detect negative-curvature directions. Equipped with this advantage, we discuss algorithms, under the general name of Newton-MR, which can be used for optimization of general non-convex objectives, and that come with favourable complexity guarantees. We also give numerical examples demonstrating the performance of these methods for large-scale non-convex machine learning problems.

optimization and control

Audience: researchers in the topic

Variational Analysis and Optimisation Webinar

Series comments: Register on www.mocao.org/va-webinar/ to receive information about the zoom connection.